package com.cfw.collection;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import javax.swing.tree.DefaultMutableTreeNode;

public class TreeSearch {
	
	/**
	 * TreeSearch를 이용한 트리 데이터 조회시 각 노드, 자식노드에 대하여 호출되는 콜백
	 */
	public static abstract class AbstractNavigateCallback {
		/**
		 * ? 
		 */
		private final Object data;
		
		public AbstractNavigateCallback(Object data) {
			this.data =	data;	
		}
		
		public Object getData() {
			return data;
		}
		
		abstract public void onnode(Object parent, Object userObject);
		abstract public Object onchild(Object parent);
	}
	
	/**
	 * TreeSearch를 이용한 트리 데이터 조회시 각 노드와 자식노드를 이동하기 위하여 호출되는 콜백
	 */
	public static abstract class AbstractNavigateSourceCallback {
		/**
		 * ?
		 */
		private final Object data;
		
		public AbstractNavigateSourceCallback(Object data) {
			this.data =	data;	
		}
		
		public Object getData() {
			return data;
		}
		
		abstract public boolean isLeaf(Object node);
		abstract public Object getNextSibling(Object node);
		abstract public Object getUserObject(Object node);
		abstract public Object getFirstChild(Object node);
	}	
	
	abstract static public class AbstractSearchMatchCallback {
		abstract public boolean match(MapTree mapTree);
	}
	
		@SuppressWarnings("unchecked")
		public static void logging(final String tag, final Object... pars) {
			final StringBuffer buf =	new StringBuffer();
			
			buf.append(String.format("*** [%-20s]", tag));
			
			if (pars.length > 0) {
				for (int i = 0; i < pars.length; i++) {
					if (pars[i] == null) {
						buf.append(" *** null");
					} else
					if (pars[i] instanceof DefaultMutableTreeNode) {
						final DefaultMutableTreeNode node =	(DefaultMutableTreeNode)pars[i];
						
						if (node.getUserObject() != null) {
							Map<String, String> map =	(Map<String, String>)node.getUserObject();
							buf.append(String.format(" *** [%-30s]", map.toString()));
						}
					} else {
						buf.append(String.format(" *** [%-30s]", pars[i].toString()));
					}
				}
			}
			System.out.println(buf.toString());
		}
	
	/**
	 * DefaultMutableTreeNode에 대한 트리탐색
	 * @param tree
	 */
	public static void navigate(final DefaultMutableTreeNode tree) {
		DefaultMutableTreeNode ref = tree;
		final Stack<DefaultMutableTreeNode> stack = new Stack<DefaultMutableTreeNode>();
		while (ref != null) {
			logging("data", ref);
			
			// 최하위노드까지 이동, 이동 중 부모노드들은 스택에 보관 
			if (ref.isLeaf()) { // 최하위노드라면, Sibling들을 탐색
				logging("data.leaf");
				
				ref = ref.getNextSibling();
				
				// Sibling이 없다면, 해당 level에서 수행할 내용 없으므로, pop으로 그 이전의 node에 대하여 처리
				while (ref == null && stack.size() > 0) {
					DefaultMutableTreeNode pre = stack.pop();
					ref = pre.getNextSibling();
					
					logging("pop", stack);
				}
			} else { // 최하위노드가 아니라면, 스택에 현재 노드를 보관
				logging("data.has-child");
				
				stack.push(ref);
				ref = (DefaultMutableTreeNode)ref.getFirstChild();
				
				logging("push", stack);
			}
			
			if (ref == null) {
				logging("ref-isnull", stack);
			}
		}
	}
	
		private static Object getNewSibling(final AbstractNavigateCallback method, final Map<MutableKeyHolder, MutableKeyHolder> parentMap, final MutableKeyHolder child) 
				throws IllegalArgumentException {
			if (parentMap == null) { throw new IllegalArgumentException("parentMap can't be null"); }
			
			final MutableKeyHolder parent =	parentMap.get(child);
			
			if (parent == null) { throw new IllegalArgumentException("parent can't be null"); }
			
			final Object object = parent.getObject();
			
			if (object == null) { throw new IllegalStateException("parent node parameter of onchild method can't be null"); }
			
			return method.onchild(object); 
		}

		private static void inspectMap(final Map<MutableKeyHolder, MutableKeyHolder> parentMap) {
			if (parentMap == null) {
				System.out.println("%%% paretMap is null");
			}
			
			final Set<MutableKeyHolder> keySet = 		parentMap.keySet();
			final Iterator<MutableKeyHolder> iterator =	keySet.iterator();

			while (iterator.hasNext()) {
				MutableKeyHolder key =	iterator.next();
				Object value =			parentMap.get(key);	 
				System.out.println("%%% key.getObject() %%% " + key.getObject() + " %%% ISNULL %%% " + (value == null));
			}
		}
		
	public static void navigate(final DefaultMutableTreeNode tree, final AbstractNavigateCallback method) {
		if (method == null) {
			throw new IllegalArgumentException("method can't be null");
		}
		
		final Stack<DefaultMutableTreeNode> stackTree =	
										new Stack<DefaultMutableTreeNode>();
		final Stack<MutableKeyHolder> stackHolder =	
										new Stack<MutableKeyHolder>();
		final HashMap<MutableKeyHolder, MutableKeyHolder> parentMap =
										new HashMap<MutableKeyHolder, MutableKeyHolder> ();
		
		DefaultMutableTreeNode 	ref =	tree;
		Object o =						method.getData();
		MutableKeyHolder holder =		new MutableKeyHolder(o);
		MutableKeyHolder parentHolder =	null;
		
		while (ref != null) {
			if (ref == null || o == null) {
				throw new IllegalStateException("data object or tree object parameter of onnode method can't be null");
			}
			method.onnode(o, ref.getUserObject());

			if (ref.isLeaf()) {
				logging("data.leaf", ref);
				
				ref = 	ref.getNextSibling();
				
				// Sibling이 없다면, 해당 level에서 수행할 내용 없으므로, pop으로 그 이전의 node에 대하여 처리
				while (ref == null && stackTree.size() > 0) {
					ref =	stackTree.pop().getNextSibling();
					
					holder =	stackHolder.pop();
					
					{ // logging
						logging("pop", holder);
						
						Object tmpObj =	(holder == null ? null : holder.getObject());
						
						if (tmpObj == method.getData()) {
							logging("object is top");
						}
						
						logging("after.pop.stackTree", stackTree);
						logging("top", method.getData());
					}
				}
				
				// holder는 현재 target객체 위치, holder의 parent 접근 목적
				// 반환값는 값을 담기위한 새로운 target객체
				// ref이 null인 상태는 처리해야 할 데이터가 없는 상태 
				if (ref != null) {
					o = 		getNewSibling(method, parentMap, holder);
					holder =	new MutableKeyHolder(o);
				}
			} else {
				logging("data.has-child", ref);
				
				stackTree.push(ref);
				ref = (DefaultMutableTreeNode)ref.getFirstChild();
				
				// 1. parentMap에는 생성된 child가 loop 종료전 put되어야 한다.
				// 2. stack2에 push되는 자료는 parentMap의 key여야 한다.
				// 3. stack2에 push되는 자료는 parentMap의 key로 모두 존재하여야 한다.
				stackHolder.push(holder);
				parentMap.put(holder, parentHolder);
				parentHolder =	holder;

				Object parent =		o;
				
				if (parent == null) { throw new IllegalStateException("parent node parameter of onchild method can't be null"); }
				
				o = method.onchild(parent);
				
				holder = new MutableKeyHolder(o);
				if (!parentMap.containsKey(holder)) {
					parentMap.put(holder, new MutableKeyHolder(parent));
				}

				{ // loggging
					inspectMap(parentMap);
					logging("stackHolder.size:", stackHolder.size());
					
					logging("after.push.stackTree", stackTree);
				}
			}
		}
	}	
	
	public static void navigate(final MapTree tree, final AbstractNavigateCallback method) {
		if (method == null) {
			throw new IllegalArgumentException("method can't be null");
		}
		
		final Stack<MapTree> stackTree =	
										new Stack<MapTree>();
		final Stack<MutableKeyHolder> stackHolder =	
										new Stack<MutableKeyHolder>();
		final HashMap<MutableKeyHolder, MutableKeyHolder> parentMap =
										new HashMap<MutableKeyHolder, MutableKeyHolder> ();
		
		MapTree ref =					tree;
		Object o =						method.getData();
		MutableKeyHolder holder =		new MutableKeyHolder(o);
		MutableKeyHolder parentHolder =	null;
		
		while (ref != null) {
			if (ref == null || o == null) {
				throw new IllegalStateException("data object or tree object parameter of onnode method can't be null");
			}
			method.onnode(o, ref.getUserObject());

			if (ref.isLeaf()) {
				logging("data.leaf", ref);
				
				ref = 	ref.getNextSibling();
				
				// Sibling이 없다면, 해당 level에서 수행할 내용 없으므로, pop으로 그 이전의 node에 대하여 처리
				while (ref == null && stackTree.size() > 0) {
					ref =	stackTree.pop().getNextSibling();
					
					holder =	stackHolder.pop();
					
					{ // logging
						logging("pop", holder);
						
						Object tmpObj =	(holder == null ? null : holder.getObject());
						
						if (tmpObj == method.getData()) {
							logging("object is top");
						}
						
						logging("after.pop.stackTree", stackTree);
						logging("top", method.getData());
					}
				}
				
				// holder는 현재 target객체 위치, holder의 parent 접근 목적
				// 반환값는 값을 담기위한 새로운 target객체
				// ref이 null인 상태는 처리해야 할 데이터가 없는 상태 
				if (ref != null) {
					o = 		getNewSibling(method, parentMap, holder);
					holder =	new MutableKeyHolder(o);
				}
			} else {
				logging("data.has-child", ref);
				
				stackTree.push(ref);
				ref =	(MapTree)ref.getFirstChild();
				
				// 1. parentMap에는 생성된 child가 loop 종료전 put되어야 한다.
				// 2. stack2에 push되는 자료는 parentMap의 key여야 한다.
				// 3. stack2에 push되는 자료는 parentMap의 key로 모두 존재하여야 한다.
				stackHolder.push(holder);
				parentMap.put(holder, parentHolder);
				parentHolder =	holder;

				Object parent =		o;
				
				if (parent == null) {
					throw new IllegalStateException("parent node parameter of onchild method can't be null");
				}
				
				o = method.onchild(parent);
				
				holder =	new MutableKeyHolder(o);
				if (!parentMap.containsKey(holder)) {
					parentMap.put(holder, new MutableKeyHolder(parent));
				}

				{ // loggging
					inspectMap(parentMap);
					logging("stackHolder.size:", stackHolder.size());
					
					logging("after.push.stackTree", stackTree);
				}
			}
		}
	}	
	
		private static void loggingSourceNTarget(Stack<Object> stackSource, Object target, MutableKeyHolder holder) {
			logging("pop", holder);
			
			Object tmpObj =	(holder == null ? null : holder.getObject());
			
			if (tmpObj == target) { logging("object is top"); }
			
			logging("after.pop.stackTree", stackSource);
			logging("top", target);
		}

		private static MutableKeyHolder getNewSibling(final AbstractNavigateCallback method, final MutableKeyHolder parent) 
				throws IllegalArgumentException {
			if (parent == null) { throw new IllegalArgumentException("parent can't be null"); }
			
			final Object object = parent.getObject();
			
			if (object == null) { throw new IllegalStateException("parent node parameter of onchild method can't be null"); }
			
			Object target = method.onchild(object); 
			
			return new MutableKeyHolder(target);
		}
		
	@SuppressWarnings("unused")
	public static void navigate(final AbstractNavigateSourceCallback srcCallBack, final AbstractNavigateCallback callBack) {
		if (srcCallBack == null || callBack == null) { throw new IllegalArgumentException("Navigate call back can't be null"); }
		
		// 자식노드로 탐색시 현재노드를 스택에 push, 자식노드의 탐색 종료 후 pop
		final Stack<Object> stackSource = new Stack<Object>(); 
		// 소스로부터 탐색된 데이터가 콜백에 의해 가공 저장되는데, 이 데이터에 대한 탐색시 사용될 스택
		final Stack<MutableKeyHolder> stackTarget = new Stack<MutableKeyHolder>(); 
		final HashMap<MutableKeyHolder, MutableKeyHolder> parentMap = new HashMap<MutableKeyHolder, MutableKeyHolder> (); // 
		
		Object source = srcCallBack.getData(); // 탐색대상 객체, 탐색시 자식노드로 참조가 재할당된다.
		//Object target = callBack.getData(); // 탐색결과 객체
		MutableKeyHolder target = new MutableKeyHolder(callBack.getData()); // target객체에 대한 탐색참조객체생성
		MutableKeyHolder parentTarget =	null;
		
		while (source != null) {
			if (source == null || target.getObject() == null) { throw new IllegalStateException("data object or tree object parameter of onnode method can't be null"); }
			
			callBack.onnode(target.getObject(), srcCallBack.getUserObject(source));

			if (srcCallBack.isLeaf(source)) {
				logging("data.leaf", source);
				
				source = srcCallBack.getNextSibling(source);
				
				// 다음 Sibling 또는 모든 Sibling에 대하여 처리하였다면, 스택에서 상위노드를 pop
				// - Sibling이 없다면, 해당 level에서 수행할 내용 없으므로, pop으로 그 이전의 node에 대하여 처리
				while (source == null && stackSource.size() > 0) {
					source = stackSource.pop();
					
					if (source == null) { throw new IllegalStateException("Source object Stack.pop return null"); }
					
					target = stackTarget.pop();
					source = srcCallBack.getNextSibling(source);
					
					loggingSourceNTarget(stackSource, callBack.getData(), target); // logging
				}
				
				// 위의 반복문으로 source는 현재 처리할 위치로 이동한 상태 (다음 Sibling, 또는 상위노드) 
				// holder는 현재 target객체 위치, holder의 parent 접근 목적
				// 반환값는 값을 담기위한 새로운 target객체
				// ref이 null인 상태는 처리해야 할 데이터가 없는 상태 
				if (source != null) {
					target = getNewSibling(callBack, parentMap.get(target));
				}
			} else {
				logging("data.has-child", source);
				
				stackSource.push(source);
				source = srcCallBack.getFirstChild(source);	
				
				// 1. parentMap에는 생성된 child가 loop 종료전 put되어야 한다.
				// 2. stack2에 push되는 자료는 parentMap의 key여야 한다.
				// 3. stack2에 push되는 자료는 parentMap의 key로 모두 존재하여야 한다.
				stackTarget.push(target);
				parentMap.put(target, parentTarget);
				parentTarget = target;

				if (parentTarget.getObject() == null) { throw new IllegalStateException("parent node parameter of onchild method can't be null"); }

				//
//				Object target = callBack.onchild(parentHolder.getObject());
//				holder = new MutableKeyHolder(target);
//				if (!parentMap.containsKey(holder)) {
//					parentMap.put(holder, new MutableKeyHolder(parent));
//				}


				{ // loggging
					inspectMap(parentMap);
					logging("stackHolder.size:", stackTarget.size());
					
					logging("after.push.stackTree", stackSource);
				}
			}
		}
	}			
}

/**
 * 가변객체를 맵의 키로 사용하기 위한 어댑터객체
 * - hashcode가 변동되기 때문에 맵을 맵의 키로 사용할 수 없다. 그러므로 object 애트리뷰트에 비교될 객체를 지정하고,
 * 맵의 get 메서드의 리턴에 사용될 equals, hashCode 메서드를 Override 함      
 * @author hipark
 *
 */
final class MutableKeyHolder {
	private static final int HASH_CODE = 2147483647;
	private final Object object;
	
	public MutableKeyHolder(final Object object) { this.object = object; }
	
	public Object getObject() { return object; }
	
	@Override
	public boolean equals(Object object) {
		if (this == object) { return true; }
		if (object == null) { return false; }
		if (!(object instanceof MutableKeyHolder)) { return false; }
		
		MutableKeyHolder other = (MutableKeyHolder)object;
		if (getObject() != other.getObject()) { return false; }
		
		return true;		
	}
	
	@Override
	public int hashCode() { return HASH_CODE; }
}